package com.sk.leetcode.arithmetic;

import java.util.List;

/**
 * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
 * 说明：
 * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
 * 示例 1:
 * <p>
 * 输入: root = [3,1,4,null,2], k = 1
 * ..3
 * ./ \
 * 1   4
 * .\
 * ..2
 * 输出: 1
 * 示例 2:
 * <p>
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 * ........5
 * ...../     \
 * ....3      100
 * .../ \     /  \
 * ..2   4   90  110
 * ./
 * 1
 * 输出: 3
 * 说明：二叉树按照左小右大的规则排序(题上没说明，但是乱放会给出错误数据)
 * <p>
 * 进阶：
 * 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
 */
public class Test230 {


    private static Integer value = null;

    public static void main(String[] args) {
        Integer[] root = {5, 3, 6, 2, 4, null, null};
        List<TreeNode> nodes = Test124.suan(root);
        int res = kthSmallest2(nodes.get(0), 5);
        System.out.println(res);
    }

    /**
     * 后续优化
     *
     * @param root
     * @param k
     * @return
     */
    public static int kthSmallest2(TreeNode root, int k) {
        Res res = new Res();
        js2(root, k, res);
        return res.getRes();
    }

    private static void js2(TreeNode root, int k, Res res) {
        if(root.left == null) {
            res.setVPlus();
        } else {
            js2(root.left, k, res);
            res.setVPlus();
        }
        if(res.getRes() == null && res.getV() == k) {
            res.setRes(root.val);
            return;
        } else if(res.getRes() != null) {
            return;
        }
        if(root.right == null) {
            return;
        } else {
            js2(root.right, k, res);
        }
        if(res.getRes() == null && res.getV() == k) {
            res.setRes(root.val);
            return;
        }
    }


    public static int kthSmallest(TreeNode root, int k) {
        js(root, k, 0);
        int res = value;
        value = null;
        return res;
    }

    private static int js(TreeNode root, int k, int v) {
        if(root.left == null) {
            v++;
        } else {
            v = js(root.left, k, v) + 1;
        }
        if(v == k && value == null) {
            value = root.val;
        }
        if(root.right == null) {
            return v;
        } else {
            v = js(root.right, k, v);
        }
        if(v == k && value == null) {
            value = root.val;
        }
        return v;
    }

}

class Res {
    private Integer res;
    private int v;

    public Integer getRes() {
        return res;
    }

    public void setRes(Integer res) {
        this.res = res;
    }

    public int getV() {
        return v;
    }

    public void setVPlus() {
        v++;
    }
}